package prac9;

import java.math.BigInteger;


public class Prac9 {

	
//	public static BigInteger binomialIter(int n, int r){
//		BigInteger result = new BigInteger("1");
//		BigInteger fraction =  new BigInteger("1");
//		BigInteger denominator = new BigInteger("1");;
//		long i = n-r;
//		while (n>1){
//			BigInteger nPrime = new BigInteger(String.valueOf(n));
//			fraction = fraction.multiply(nPrime);
//			n--;
//		}
//		while (r > 1 && i > 1){
//			BigInteger rPrime = new BigInteger(String.valueOf(r));
//			BigInteger iPrime = new BigInteger(String.valueOf(i));
//			denominator = denominator.multiply(rPrime).multiply(iPrime);
//			r--;
//			i--;
//		}
//		if(r >= i){
//			while(r>1){
//				BigInteger rPrime = new BigInteger(String.valueOf(r));
//				denominator = denominator.multiply(rPrime);
//				r--;
//			}
//		} else{
//			while(i>1){
//				BigInteger iPrime = new BigInteger(String.valueOf(i));
//				denominator = denominator.multiply(iPrime);
//				i--;
//			}
//		}
//		result = fraction.divide(denominator);
//		return result;
//	}
	public static long factorial(int n){
		long result = 1;
		while(n>1){
			result = result *n;
			n--;
		}
		return result;
	}
	
	
	/**
	 * Factorial formula for computing the value of binomial coefficients
	 * (Referred to as 'Method 1')
	 * 
	 * @pre			n and r must be nonnegative integers and r must be equal to or less than n
	 * @post		the binomial coefficient indexed by n and r is computed
	 * @param		n the first nonnegative integer index for the binomial coefficient
	 * @param		r the second nonnegative integer index for the binomial coefficient
	 * @complexity	Best and worst case the complexity of {@link #factorial(int)} which 
	 * 				equates to O(N) where N is the value of n
	 * @return
	 */
	public static long binomialIter(int n, int r){
		return (long)((factorial(n))/ ((double) factorial(n-r) * factorial(r)));
	}
	
	/**
	 * Multiplicative formula for computing the value of binomial coefficients
	 * (Referred to as 'Method 2')
	 * 
	 * @pre n and r must be nonnegative integers and r must be equal to or less than n
	 * @post the binomial coefficient indexed by n and r is computed
	 * @param n the first nonnegative integer index for the binomial coefficient
	 * @param r the second nonnegative integer index for the binomial coefficient
	 * @complexity	Best case O(1) when r = 0 or r = n
	 * 				Worst case of O(N) 
	 * 				where	N is the value of r
	 * @return
	 */
	public static long  binomialProd(int n, int r){
		if (r == 0 || r == n) {
			return 1;
		} else {
			double result = 1;
			while (r >= 1){
				double intermediate = (double)n/r;
				result = result * intermediate;
				n--;
				r--;
			}
			return (long)result;
		}
	}
	
	
	/**
	 * Recursively formula for computing the value of binomial coefficients
	 * (Referred to as 'Method 3')
	 * 
	 * @pre 		n and r must be nonnegative integers and r must be equal to or less than n
	 * @post 		the binomial coefficient indexed by n and r is computed
	 * @param n 	the first nonnegative integer index for the binomial coefficient
	 * @param r 	the second nonnegative integer index for the binomial coefficient
	 * @complexity	best case of O(1) when n = r or r = 0
	 * 				Worst case of O(2^(N-1)) 
	 * 			    where	N is the value of n
	 * @return
	 */
	public static long binomialRec(int n, int r){
		if(r == 0 ) return 1;
		if(n == r ) return 1;
		long result = binomialRec(n-1, r-1) + binomialRec(n-1, r);
		return result;
	}
	
	/**
	 * Method to test each formula of computing the binomial coefficient and display results with elapsed time per computating per formula
	 * @pre n/a
	 * @post a table is printed showing results of each formula using N and N/2 with the elapsed time for each computation
	 * @complexity Best and worst case of the method with the biggest complexity which is {@link #binomialRec(int, int)}
	 */
	public static void runBinomials(){
		int n=1;
		System.out.println("N\t" + "Result\t"+ "Timetaken" );
		while(n<=100){
			long t0,  t1,  timeTaken,  b;
			
			t0  =  System.nanoTime();
			b = binomialIter(n, n/2);
			t1  =  System.nanoTime();
			timeTaken  =  t1  -  t0;
			System.out.println(n +"\t"+ b +"\t"+ timeTaken);
			
			t0  =  System.nanoTime();
			b = binomialProd(n, n/2);
			t1  =  System.nanoTime();
			timeTaken  =  t1  -  t0;
			System.out.println(n +"\t"+ b +"\t"+ timeTaken);
			
			t0  =  System.nanoTime();
			b = binomialRec(n, n/2);
			t1  =  System.nanoTime();
			timeTaken  =  t1  -  t0;
			System.out.println(n +"\t"+ b +"\t"+ timeTaken);
			
			t0  =  System.nanoTime();
			b = binomialMin(n, n/2);
			t1  =  System.nanoTime();
			timeTaken  =  t1  -  t0;
			System.out.println(n +"\t"+ b +"\t"+ timeTaken);
			
			n++;
		}
	}
	
	
	
	/**
	 * Method to tries to reduce the errors when computing the binomial coefficients index by n and r using a multiplicative formula 
	 *
	 * @pre 		n and r must be nonnegative integers and r must be equal to or less than n
	 * @post 		the binomial coefficient indexed by n and r is computed
	 * @param n 	the first nonnegative integer index for the binomial coefficient
	 * @param r		the second nonnegative integer index for the binomial coefficient
	 * @complexity	best case of O(1) when r = n or r = 0, worst case of O(N) where N is r
	 */
	public static long binomialMin(int n, int r) {
		if (r == 0 || r == n) {
			return 1;
		} else if (r < 4) {
			double ans = 1, a = n, b = r;
			while (b > 1) {
				ans *= a/b;
				a--;
				b--;
			}
			ans *= (n-r+1);
			return (long)ans;

		} else {
			double ans = 1, a = n, b = r;
			double tmp1, tmp2;
			double i = 0;
			for (i = r; i > 4; i -= 4) {
				tmp1 = a*(a-1)*(a-2)*(a-3);
				tmp2 = b*(b-1)*(b-2)*(b-3);
				a -= 4;
				b -= 4;
				ans *= (double)tmp1/tmp2;
			}
			if (i == 1) {
				ans *= (n-r+1);
			} else if (i == 2) {
				ans *= (n-r+1);
				ans *= (double)(n-r+2)/2;
			} else if (i == 3) {
				ans *= (n-r+1);
				ans *= (double)(n-r+2)/2;
				ans *= (double)(n-r+3)/3;
			}else if (i == 4) {
				ans *= (n-r+1);
				ans *= (double)(n-r+2)/2;
				ans *= (double)(n-r+3)/3;
				ans *= (double)(n-r+4)/4;
			}
			return (long)ans;
		}
	}
	
	public static void main(String[] args){
//		System.out.println(binomialIter2(30, 15));
//		System.out.println(binomialProd(67, 33));
//		System.out.println(binomialRec(15, 7));
//		binomialMin(13, 6);
		runBinomials();
	}
	
	
	/*	Question 3
	
(a) Method 1, n = 20
	Method 2, n = 66
	Method 3, n = 30
	Method 4, n = 66

(b) Method 1 showed incorrect answer(sometimes it's a negative value) after n = 20 due to overflow (because the max number that a long data type can represent  9223372036854775807 (2^63 - 1) and the result of fraction can be negative )
	Method 2 showed value 9223372036854775807 for every n > 66 due to the max number that a double type can represent being 9223372036854775807 (2^63 - 1)
	Method 3 always computes the correct answer but gets very slow when n > 30 due to its exponential complexity
	Method 4 showed value 9223372036854775807 for every n > 66 due to the max number that a double type can represent being 9223372036854775807 (2^63 - 1)

(c) When n = 13, method 1 and method 3 returned 1716, while method 2 returned 1715. Method 4 also had some results that were very close but more exact answers than Method 2.
	This is because if n/r resulted in a recurring decimal, the answer stored would be an approximation.

		while (r >= 1){
			double intermediate = (double)n/r;
			result = result * intermediate;
			n--;
			r--;
		}

(d) The complexity of Method 1, Method 2 and Method 4 is O(N). This is reflected in the elapsed times of each method as they both take a slightly
	longer time to compute N as it increases. Method 3 shows an exponential trend in its elapsed times which agrees with its complexity of O(2^N).

 */
}


